AN549/0792 thinning digital patterns using the imsa110 application note summary page 1. introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 thinning. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 the imsa110 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2. the algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 3. discrete implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 4. a110 implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 4.1 the basic implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 4.2 a solution to the disappearing pattern problem . . . . . . . . . . . . . . . . . . 5 4.3 monitoring the progress of the operation with the statistics monitor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 5. performance assessment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 6. conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 7. implementation data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 7.1 first subiteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 7.2 second subiteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 8. references . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1. introduction 1.1 thinning thinning is a very important preprocessing stage of pattern recognition. it is a technique which ex- tracts the basic s hapes f rom images. these shapes are known as skeletons. it attempts to remove all redundant points while maintaining the basic struc- ture and connectivity of the original patterns. in [1] an algorithm is proposed and modifications to it are described in [2]. the final form of the algorithm has the advantage of being both fast, and suitable for parallel operation. 1.2 the imsa110 the imsa110 [3] is a single-chip reconfigurable and cascadable subsystem suitable for many high speed image and signal processing applications. the imsa110 consists of a configurable array of multiply-accumulators, three programmable 1120 stage shift registers, a versatile post-process- ing unit and a microprocessor interface for configu- ration and control purposes. figure 1 shows the main processing core of the device. it consists of 21 multiply accumulate stages arranged in three banks of seven. these may be configured as either a 21 stage pipeline or a 3x7 two-dimensional window. the output from the macs is fed into the backend processing unit. it is this section which allows various data transforma- tions to take place adding greatly to the flexibility of the overall device. the maximum data rate which may be applied to the inputs is 20mhz. figure 2 shows a functional block diagram of the backend post processing unit. complete details may be found in [3]. 1/8
decode logic 21 x 8-bit update coefficient registers 21 x 8-bit current coefficient registers 256 x 8-bit data transformation look up ram backend look up table usr lsr pcr0 pcr1 pcr2 bcr mmb oub tcr scr acr configuration and control registers control logic 1120 stage programmable shift register (psrb) 1120 stage programmable shift register (psra) 7-stage multiply-accumulate array b 7-stage multiply-accumulate array a 1120 stage programmable shift register (psrc) 7-stage multiply-accumulate array c d 22 22 8 22 8 8 9 clock reset cascade input cascade output psrout address psrin mem data synchronous functions enable 1 enable 2 write asynchronous functions backend post-processing unit (normalisation, saturation, and data transformation) AN549-01.eps figure 1 : imsa110 users model thinning didital patterns using the imsa110 2/8
shifter -2 to 14 shifter [8:0] cascade adder rectifier prescaler byte select min/max register comparator gt/lt over/undershoot count over/undershoot buffer min/max buffer lsr 64 x 32 bit ram 8 6 usr 32 y bus [26:22] [21:0] 32 data transformation unit 22 22 22 mux 22 22 22 22 from mac array negative overflow positive overflow cascade input pads 1 rounding 22 control statistics monitor 5 22 22 1 1 x bus 8 from bcr mux zero data 22 mux 22 1 rounding output adder 22 22 8 8 6 [21:14] [7:0] mux mux 88 [13:8] [21:14] [7:0] 22 clock cycle cascade output pads 1 2 3 4 5 6 over/under select (isbs) 2 data normaliser AN549-02.eps figure 2 : detailed block diagram of the back-end post processing unit thinning digital patterns using the imsa110 3/8
2. the algorithm consider an image im in which every pixel im(i,j) is either 0 or 1. it is normal for 0 to represent the background and 1 to represent the foreground patterns. it is assumed that each pixel im(i,j) has eight closest neighbours as shown in figure 3. p 9 pp p p p ppp 8 765 4 3 2 1 AN549-03.eps figure 3 : a pixel p 1 and its 8 closest neighbours the output of the algorithm for any given pixel only depends on the value of that pixel and its eight nearest neighbours. this allows parallel process- ing to be applied with the possibility of all the picture elements being processed simultaneously. the nature of the algorithm is iterative, each itera- tion takes the image closer to the fully thinned result. when an iteration is performed which doesnt cause any change to the image then noth- ing further can be gained by applying further itera- tions. each iteration is divided into two subitera- tions which erode the pattern or patterns to be thinned on opposite edges. in the first subiteration the pixel p 1 is deleted if all of the following criteria are satisfied: -3 b(p 1 ) 6 -a(p 1 ) = 1 -p 2 .p 4 .p 6 = 0 -p 4 .p 6 .p 8 = 0 where a(p 1 ) is the number of 0 to 1 transitions around the closed path p 2 ..p 9 and b(p 1 ) is the number of non zero neighbours of p 1 . the second subiteration is identical to the first except that the last two criteria are changed to: -p 2 .p 4 .p 8 = 0 -p 2 .p 6 .p 8 = 0 it should be noted that this algorithm is not perfect. some digital patterns will totally disappear. in fact any pattern that can be reduced to a 2 by 2 square will disappear entirely. a solution to this problem will be presented in section 4. 3 discrete implementation a number of methods of implementing thinning are available. these typically involve the use of arrays of processors such as the icl dzp (see [5]). such methods are expensive and physically large but do allow more complicated algorithms than the one presented in the previous section to be imple- mented. a simple binary thinning unit which may be built in hardware is shown below. such a unit is capable of implementing one subeteration of the algorithm described in section 2. it works by arranging for each of the address inputs of the prom to corre- spond to one of the pixels in a three pixel square region. by programming the prom with the appro- priate data, which may be calculated from the specified criteria, the output of the prom gives a new image in which the objects should have been erolded. this process is repeated until no further erosion takes place (note that alternate iterations must use alternate sets of criteria sets of criteria to obtain an unbiased operation). the performance of such a unit is considerable and it should be fairly trival to process ten million pixels per second. in addition the unit is cascadable which can considerably increase the performance of a system. it does have a number of disadvantages however : it is not a single chip solution, unless use is made of semi/full custom chip design. it is inflexible. replacing the prom with sram would improve matters but even so the range of functions such a unit can perform is very limited. 1d 1d 1d 1d 1d 1d line delay line delay 512 x 1 prom AN549-04.eps figure 4 : an alternative hardware implementation thinning didital patterns using the imsa110 4/8
4. a110 implementation 4.1. the basic implementation consider the 2-d filter kernel shown below. when a binary image composed solely of os and 1s is applied to this kernel the output consists of num- bers in the range of 0 to 511. each output uniquely identifies the pattern of os and 1s which caused it. by feedit this output into a look up table which has 512 entries it is then possible to generate the output value for p1. the look up table must be programmed with the appropriate pattern of os and 1s as defined by the criteria for one of the subiterations. 64 32 16 128 1 2 4 8 256 AN549-05.eps figure 5 : a kernel for binary thinning unfortunately such a kernel cannot be imple- mented on one imsa110. there are two reasons for this: the lut only contains 256 entries plus the upper and lower saturation registers. only coefficients between -128 and 255 mays be programmed into the mac. the first problem may be overcome by inverting the input image and programming the upper saturation register to 1 so that now any pattern with p1 deleted will give an output which is at least 256. this will cause an overselect to occur at the prescaler. the effect of this is for the lut output to be taken from the usr (upper saturation register). thus the out- put of the lut will be 1 which indicates a deleted pixel in the inverted image convention. the second problem coulb be overcome by using two imsa110s. this is achieved by superimposing the two kernels below (see [4] for details about cascading). it would be desirable however to im- plement each subiteration in a single device. 64 32 16 128 1 2 4 8 128 128 0 0 00 00 0 0 AN549-06.eps figure 6 : twin kernels for binary thinning by inspection of the criteria it may be seen that if the coefficients are changed to the kernel shown below then it is still possible to produce a valid look up table. this occurs because although there are two different patterns which can give a mac output of 127 the required lut output for each is the same. this method allows a single imsa110 to fully implement one subiteration of the thinning algo- rithm. section 7 shows the data to be programmed into the imsa110 to implement this algorithm. 64 32 16 1 2 4 8 127 255 AN549-07.eps figure 7 : a kernel for single ims a110 binary thinning 4.2. a solution to the disappearing pattern problem as mentioned in section 2 any object which thins down to a 2 by 2 pixel square will disappear entirely. this problem may be overcome by slightly modify- ing the data in the lookup tables. the first subiteration attacks objects from both below and to the left. in order to stop 2 by 2 pixel regions disappearing it is necessary to stop the elimination of the central pixel in the image seg- ment shown below. note that white indicates a pixel which is set. o do this the date at location 1f0 in the first subiteration must be set to 0. thinning digital patterns using the imsa110 5/8
an identical procedure may be applied for the second subiteration except that in this instance the date at location 11f must be set to 0. 4.3. monitoring the progress of the operation with the statistics monitor the completion of the thinning operation may be detected by using the statistics monitor in the back- end. the procedure for doing this with a single ims a110 is as follows: set the max register mmr to 254, and configure the imsa110 statistics monitor as an overshoot counter. zero the over shoot counter (ouc). perform the first subiteration. record the contents of the ouc register which now indicates the number of pixels already de- leted at the start of the iteration. perform the second subiteration. repeat from tep 2 for the next iteration, if the same value is obtained in the ouc register twice in succession then the thinning operation is com- plete since no further pixels have been deleted. the actual change in the overshoot count for each iteration may be used as an indication of the amount of progress being made. 5 performance assessment to perform a binary thinning operation on a typical AN549-08.eps figure 8 : the central pixel in this image 512 pixel square image using a single imsa110 would take just over 13 ms for each subiteration at 20 mhz (this neglects the time spent reconfiguring the look up table for the next subiteration). thus if 12 subiterations were required to fully thin an image then this would take about 156 ms. this perform- ance level is formidable byt mey be easily in- creased by cascading a number of devices to- gether (see [4]). for example if two devices were cascaded so that the first and second devices performed the first and second subiterations re- spectively then each complete iteration would still take just over 13ms. so to apply 12 subiterations with this configuration would require only 78ms. this principle may be extended to cascades con- taining any number of devices (even numbers are preferred since no lookup table reconfiguration is required). if 12 devices were cascaded then the complete thinning operation would take only 13ms. in addition the screen may be sliced up with sepa- rate portions being sent to different imsa110s or cascades of imsa110s for even greater perform- ance. the imsa110 offers other advantages when built into a system since it is capable of performing all the initial image processing commonly associated with image recognition. preprocessing filtering. edge detection. thresholding. thinning. pattern matching. 6 conclusion it has been shown how the imsa110 may be used to provide a very high performance and expand- able thinning engine. this when coupled to the other abilities of the ims a10 make the device ideal as a front end processor in many image processing or recognition systems. thinning didital patterns using the imsa110 6/8
7 implementation data 7.1. first subiteration scr 090 5c acr 092 00 cr0a 000 40 7f 01 cr0b 010 20 ff 02 cr0c 020 10 08 04 pcra 080 line length +7 pcrb 082 line length +7 pcrc 084 a suitable value to deskew the output image bcr0 0a0 01 bcr1 0a1 00 bcr2 0a2 40 bcr3 0a3 80 usr 0f8 00 00 00 01 lut 100 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 110 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 120 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 130 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 140 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 150 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 160 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 170 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 180 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 190 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 1a000000000000000000000000000000000 1b000000000000000000000000000000000 1c0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 1d0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 1e000000000000000000000000000000000 1f0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 acr 092 02 7.2. second subiteration scr 090 5c acr 092 00 cr0a 000 40 7f 01 cr0b 010 20 ff 02 cr0c 020 10 08 04 pcra 080 line length +7 pcrb 082 line length +7 pcrc 084 a suitable value to deskew the output image bcr0 0a0 01 bcr1 0a1 00 bcr2 0a2 40 bcr3 0a3 80 usr 0f8 00 00 00 01 lut 100 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 110 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 120 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 130 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 140 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 150 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 160 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 170 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 180 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 190 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 1a000000000000000000000000000000000 1b000000000000000000000000000000000 1c0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 1d0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 1e000000000000000000000000000000000 1f0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 acr 092 02 thinning digital patterns using the imsa110 7/8
8. references 1 t.y. zhang, c.y. suen _ a fast parallel algorithm for thinning digital patterns. comm. acm 27, 3. 2 h.e.ly, p.s.p. wang _ a comment on "a fast parallel algorithm for thinning digital patterns". comm. acm 29, 3. 3 imsa110 image and signal processing sub- system datasheet. 4 cascading ims a110s application note. 5 c.m. holt, a. stewart, m. clint, r.h. perrott. an improved parallel thinning algorithm. comm. acm 30, 2. information furnished is believed to be accurate and rel iable. however, sgs-thomson microelectronics assumes no responsibility for the consequences of use of such information nor for any infringement of patents or other rights of third parties which may result from its use. no licence is granted by implication or otherwise under any patent or patent rights of sgs-thomson microelectronics. specifications mentioned in this publication are subject to change without notice. this publication supersedes and replaces all information previously supplied. sgs-thomson microelectronics products are not authorized for use as critical components in lif e support devices or systems without express written approval of sgs-thomson microelectronics. ? 1994 sgs-thomson microelectronics - all rights reserved purchase of i 2 c components of sgs-thomson microelectronics, conveys a license under the philips i 2 c patent. rights to use these components in a i 2 c system, is granted provided that the system conforms to the i 2 c standard specifications as defined by philips. sgs-thomson microelectronics group of companies australia - brazil - china - france - germany - hong kong - it aly - ja pan - korea - malaysia - malta - morocco the netherlands - singapore - spain - sweden - switzerland - taiwan - thailand - united kingdom - u.s.a. thinning didital patterns using the imsa110 8/8
|
